import java.util.ArrayDeque;
import java.util.Deque;

public class LongestValidParentheses {
    // 最长的括号子串
    // https://www.nowcoder.com/practice/45fd68024a4c4e97a8d6c45fc61dc6ad?tpId=295&tqId=715&sourceUrl=%2Fexam%2Foj%3FquestionJobId%3D10%26subTabName%3Donline_coding_page
    public int longestValidParentheses (String s) {
        // write code here
        Deque<Integer> stack = new ArrayDeque<>();
        stack.addLast(-1);
        char[] c = s.toCharArray();
        int maxLength = 0;
        for (int i = 0; i < c.length; i++) {
            if (c[i] == '(') {
                stack.push(i);
            } else {
                stack.pop();
                if (stack.isEmpty()) {
                    stack.push(i);
                } else {
                    maxLength = Math.max(maxLength, i-stack.peek());
                }
            }
        }
        return maxLength;
    }

    public int longestValidParentheses2 (String s) {
        // write code here
        char[] c = s.toCharArray();
        int left  = 0;
        int right =  0;
        int maxLength  = 0;
        for (int i = 0; i < c.length; i++) {
            if (c[i] == '(') {
                left++;
            } else {
                right++;
            }
            if (right > left) {
                left = right = 0;
            } else if (left == right) {
                maxLength = Math.max(maxLength, right * 2);
            }
        }
        left = right = 0;
        for (int i = c.length-1; i >= 0; i--) {
            if (c[i] == '(') {
                left++;
            } else  {
                right++;
            }
            if (left > right) {
                left = right = 0;
            } else if (left == right) {
                maxLength = Math.max(maxLength, left * 2);
            }
        }
        return maxLength;
    }
}
